import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution02 {
	//不同层的结点用不同的队列存储
	public List<Integer> largestValues(TreeNode root){
		//存储当前层结点
		Queue<TreeNode> curNodes = new LinkedList<>();
		//存储当前层的下一层结点
		Queue<TreeNode> nextNodes = new LinkedList<>();
		List<Integer> results = new LinkedList<>();
		int maxVal = Integer.MIN_VALUE;
		boolean isFirst = true;

		if(root == null){
			return results;
		}
		curNodes.offer(root);
		while(!curNodes.isEmpty()){
			TreeNode curNode = curNodes.poll();
			if(isFirst){
				maxVal = curNode.val;
				isFirst = false;
			} else {
				maxVal = Math.max(maxVal, curNode.val);
			}
			if(curNode.left != null){
				nextNodes.offer(curNode.left);
			}
			if(curNode.right != null){
				nextNodes.offer(curNode.right);
			}
			if(curNodes.isEmpty()){
				results.add(maxVal);
				curNodes = nextNodes;
				nextNodes = new LinkedList<>();
				isFirst = true;
			}
		}
		
		return results;
	}
}
